package com.simonf.dynamic_programing;

/**
 * Created with IntelliJ IDEA.
 *
 * @Author: smionf
 * @Date: 2024/02/18/20:42
 * @Description:
 */
public class LC70ClimbStairs {
    //爬第n阶楼梯的解法数量等同于爬第n-1阶和n-2阶楼梯的和
    public int climbStairs(int n) {
    //n = 1,1种。
    //n=2,1+1,2,两种

    //n = 4
    //1 + 1 + 1 + 1
    //2 + 1 + 1
    //1 + 2 + 1
    //1 + 1 + 2
    //2 + 2

        if (n == 1)
            return 1;
        if (n == 2)
            return 2;
        long fa = 1, fb = 2, result = 0;
        for (int i = 3; i <= n; i++) {
            result = fa + fb;
            fa = fb;
            fb = result;
        }
        return (int)result;
    }
}

